// 2116. 判断一个括号字符串是否有效
// AC: https://leetcode.cn/problems/check-if-a-parentheses-string-can-be-valid/submissions/614643407/

class Solution {
public:
    bool canBeValid(string s, string locked) {
        int n=s.size();
        if(n%2)
            return 0;
        int ans=0,res=0;
        if((s[0]==')'&&locked[0]=='1')||(s[n-1]=='('&&locked[n-1]=='1'))
            return 0;
        for(int i=0;i<n;++i){
            if(locked[i]=='1'){
                if(s[i]=='(')
                    ans++;
                else if(ans)
                    ans--;
                else if(res)
                    res--;
                else
                    return 0;
            }
            else
                res++;
        }
        if(res>=ans){
            ans=0,res=0;
            for(int i=n-1;i>=0;--i){
            if(locked[i]=='1'){
                if(s[i]==')')
                    ans++;
                else if(ans)
                    ans--;
                else if(res)
                    res--;
                else
                    return 0;
            }
            else
                res++;
        }
        }
    return res>=ans;
    }
};